class Node:
    def __init__(self, data, left=None, right=None):
        self.data, self.left, self.right = data, left, right


class BinTree:
    def __init__(self, root=None):
        self.root = root
        self.callback = []

    @classmethod
    def build_from(cls, node_list):
        """通过节点信息构造二叉树
        第一次遍历我们构造 node 节点
        第二次遍历我们给 root 和 孩子赋值

        :param node_list: {'data': 'A', 'left': None, 'right': None, 'is_root': False}
        """
        node_dict = {}
        root = None
        for node_data in node_list:
            node_dict[node_data['data']] = Node(node_data['data'])  # 所有节点写入节点字典中
        for node_data in node_list:
            data = node_data['data']
            node = node_dict[data]  # node_dict = {'A':Node('A')}
            if node_data['is_root']:
                root = node
            node.left = node_dict.get(node_data['left'])  # Node('A').left = Node('B') else None
            node.right = node_dict.get(node_data['right'])
        return cls(root)

    def preorder_traverse(self, subtree):
        '''
        先(根)序遍历
        :param subtree:
        :return:
        '''

        if subtree is not None:  # 该节点没有子节点就停止
            print(subtree.data)
            self.preorder_traverse(subtree.left)
            self.preorder_traverse(subtree.right)

    def midorder_traverse(self, subtree):
        '''
        中(根)序遍历
        :param subtree:
        :return:
        '''
        if subtree is not None:  # 该节点没有子节点就停止
            self.preorder_traverse(subtree.left)
            print(subtree.data)
            self.preorder_traverse(subtree.right)

    def lastorder_traverse(self, subtree):
        '''
        后(根)序遍历
        :param subtree:
        :return:
        '''
        if subtree is not None:
            self.lastorder_traverse(subtree.left)
            self.lastorder_traverse(subtree.right)
            self.callback.append(subtree.data)

    def reverse(self, subtree):
        if subtree is not None:
            subtree.left, subtree.right = subtree.right, subtree.left
            self.reverse(subtree.left)
            self.reverse(subtree.right)


node_list = [
    {'data': 'A', 'left': 'B', 'right': 'C', 'is_root': True},
    {'data': 'B', 'left': 'D', 'right': 'E', 'is_root': False},
    {'data': 'D', 'left': None, 'right': None, 'is_root': False},
    {'data': 'E', 'left': 'H', 'right': None, 'is_root': False},
    {'data': 'H', 'left': None, 'right': None, 'is_root': False},
    {'data': 'C', 'left': 'F', 'right': 'G', 'is_root': False},
    {'data': 'F', 'left': None, 'right': None, 'is_root': False},
    {'data': 'G', 'left': 'I', 'right': 'J', 'is_root': False},
    {'data': 'I', 'left': None, 'right': None, 'is_root': False},
    {'data': 'J', 'left': None, 'right': None, 'is_root': False},
]


def Bintree(node_list):
    nodes = {}
    datas = []
    root = None
    for nodedata in node_list:
        data = nodedata['data']
        left = nodedata['left']
        right = nodedata['right']
        nodes[data] = Node(data, left, right)
        datas.append(data)
        # 所有节点均有了，nodes= {'A':Node('A'),'B':Node('B')}
        # Node('A'):{'data':'A',left:'B',right:'C'}
    for nodedata in node_list:
        data = nodedata['data']  # 'A','B','C'
        node = nodes[data]
        if nodedata['is_root']:
            root = node
        try:
            node.left = nodes[node.left]
        except KeyError:
            node.left = None
        node.right = nodes.get(nodedata['right'])

    return root


def preorder(node):
    """
       1. 利用栈，对每一个结点，先输入结点内容；
       2. 若右子树不为空，右子树压栈；
       3. 若左子树不为空，左子树压栈。
    """

    """
    if node is None:
        return
    myStack = [node]
    while myStack:
        node = myStack.pop()
        print(node.data)
        if node.right:
            myStack.append(node.right)
        if node.left:
            myStack.append(node.left)

    """
    if node is None:
        return
    myStack = []
    while myStack or node:

        if node:
            print(node.data)
            myStack.append(node)
            node = node.left
        else:
            node = myStack.pop()
            node = node.right


def midorder(node):
    """
    左子树不断入栈直到没有左子树，输出当前结点内容并指向右子树
    """
    if node is None:
        return
    myStack = []
    while myStack or node:
        if node:
            myStack.append(node)
            node = node.left
        else:
            node = myStack.pop()
            print(node.data)
            node = node.right


def lastorder(node):
    """
   后序遍历对比中序遍历难度要增大很多。
   1、因为中序遍历节点序列有一点的连续性，而后续遍历则感觉有一定的跳跃性。
   2、先左，再右，最后才中间节点；访问左子树后，需要跳转到右子树，右子树访问完毕了再回溯至根节点并访问之
    """
    if node == None:
        return
    stack1 = [node]
    stack2 = []
    while stack1:
        # 这个while循环用户找到后续遍历的逆序，存在stack2中
        node = stack1.pop()
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
        stack2.append(node)
    while stack2:
        print(stack2.pop().data)


if __name__ == '__main__':
    btree = BinTree.build_from(node_list)
    # btree.preorder_traverse(btree.root)  # 输出 A, B, D, E, H, C, F, G, I, J
    # btree.midorder_traverse(btree.root)
    # btree.lastorder_traverse(btree.root)
    # print(btree.callback)
    # btree.reverse(btree.root)
    # print(btree.root)
    preorder(btree.root)
    print('*' * 30)
    midorder(btree.root)
    print('*' * 30)
    lastorder(btree.root)
